import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * 772. 基本计算器 III
 */
public class No772 {
    /**
     * 1. 中缀表达式转换为逆波兰表达式 + 后缀表达式求值
     */
    public int calculate(String s) {
        Deque<Character> stack = new LinkedList<>();
        List<String> exp = new LinkedList<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (Character.isDigit(c)) {
                StringBuilder sb = new StringBuilder();
                while (i < s.length() && Character.isDigit(s.charAt(i))) {
                    sb.append(s.charAt(i));
                    i++;
                }
                i--;
                exp.add(sb.toString());
            } else if (c == ' ') continue;
            else if (c == '(') {
                stack.push(c);
            } else if (c == ')') {
                while (stack.peek() != '(') {
                    exp.add(stack.pop() + "");
                }
                stack.pop();
            } else {
                while (!stack.isEmpty()) {
                    if (getPriority(stack.peek()) >= getPriority(c)) {
                        exp.add(stack.pop() + "");
                    } else break;
                }
                stack.push(c);
            }
        }
        while (!stack.isEmpty()) exp.add(stack.pop() + "");
        return evalRPN(exp);
    }

    /**
     * 2. 中缀表达式转换为逆波兰表达式 + 后缀表达式求值
     */
    public int calculate2(String s) {
        return evalRPN(toRPN(s));
    }

    // 将中缀表达式转换为逆逆波兰表达式
    // 通用计算器：操作符包含了'+', '-', '*', '/'
    public List<String> toRPN(String s) {
        char[] chs = s.toCharArray();
        int n = chs.length;
        // 符号栈
        Deque<String> stack = new LinkedList<>();
        // 存储转换结果
        ArrayList<String> result = new ArrayList<>();
        // 缓存变量  - 用来对多位数进行处理
        StringBuilder temp = new StringBuilder();

        for (int i = 0; i < n; i++) {
            //System.out.print((char)chs[i] + " ");
            // 遇到空格, 直接跳过
            if (chs[i] == ' ') continue;

            // 遇到了数字, 直接输出, 但是要主要多位数的处理
            if (Character.isDigit(chs[i])) {
                // 清空缓存数据
                temp.delete(0, temp.length());
                // 多位数处理
                while (i < n && Character.isDigit(chs[i])) {
                    temp.append(chs[i]);
                    i++;
                }
                i--;
                result.add(temp.toString());
            }
            // 遇到左括号, 直接进栈
            else if (chs[i] == '(') {
                stack.push("(");
            }
            // 遇到')'不断出栈, 直到遇到'('括号或栈为空
            else if (chs[i] == ')') {
                while (!stack.isEmpty() && !"(".equals(stack.peek())) {
                    result.add(stack.pop());
                }
                // 弹出'('
                if (!stack.isEmpty())
                    stack.pop();
            }
            // 遇到 '+', '-', '*', '/'操作符, 需要根据运算优先级进行相应处理
            else {
                // 1. 若栈为空, 栈顶元素为'(', 并且当前操作符大于栈顶运算符, 则直接进栈
                // 3. 当前操作符小于或等于栈顶运算符, 则不断进行出栈, 直到满足条件1
                while (!stack.isEmpty() && !"(".equals(stack.peek()) && getPriority(chs[i]) <= getPriority(stack.peek().charAt(0))) {
                    result.add(stack.pop());
                }
                stack.push(String.valueOf(chs[i]));
            }

        }

        while (!stack.isEmpty()) result.add(stack.pop());
        return result;
    }

    /**
     * 返回运算符优先级
     */
    public int getPriority(char c) {
        return switch (c) {
            case '+', '-' -> 1;
            case '*', '/' -> 2;
            default -> 0;
        };
    }

    /**
     * 计算逆波兰表达式
     */
    public int evalRPN(List<String> tokens) {
        Deque<Integer> stack = new LinkedList<>();
        for (String token : tokens) {
            stack.push(switch (token) {
                case "+" -> stack.pop() + stack.pop();
                case "-" -> {
                    Integer suf = stack.pop();
                    yield stack.pop() - suf;
                }
                case "*" -> stack.pop() * stack.pop();
                case "/" -> {
                    Integer suf = stack.pop();
                    yield stack.pop() / suf;
                }
                default -> Integer.parseInt(token);
            });
        }
        return stack.peek();
    }
}
